package reviewAlgorithms.greedyThought;

import java.util.*;

public class PartitionLabels {
    public static void main(String[] args) {
        String str = "ababcbacadefegdehijhklij";
        System.out.println(partitionLabels(str));
    }
    public static List<Integer> partitionLabels(String str) {
        List<Integer> resList = new ArrayList<>();
        Map<Character,int[]> characterMap = new HashMap<>();
        Queue<Character> characterQueue = new PriorityQueue<>(Comparator.comparingInt(o -> characterMap.get(o)[0]));
        if (str == null || str.length() < 1) {
            return resList;
        }
        for (int i = 0; i < str.length(); i++) {
            if (characterMap.keySet().contains(str.charAt(i))){
                characterMap.get(str.charAt(i))[1] = i;
            }else {
                int[] temp = new int[2];
                temp[0] = i;
                temp[1] = i;
                characterMap.put(str.charAt(i),temp);
            }
        }
        characterQueue.addAll(characterMap.keySet());
        int start = 0;
        int end = 0;
        if (!characterQueue.isEmpty()) {
            char ch = characterQueue.poll();
            int[] temp = characterMap.get(ch);
            start = temp[0];
            end = temp[1];
        }
        while (!characterQueue.isEmpty()){
            char ch = characterQueue.poll();
            int[] temp = characterMap.get(ch);
            if (end > temp[0]){
                if (temp[1] > end){
                    end = temp[1];
                }
            }else {
                resList.add(end - start + 1);
                start = temp[0];
                end = temp[1];
            }

        }
        resList.add(str.length() - start);
        return resList;
    }
}
